package org.cabbage.lintcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class MajorityNumber {

    public static void main(String[] args) {
        MajorityNumber mn = new MajorityNumber();
        List<Integer> nums = Arrays.asList(1, 1, 1, 5, 3, 3, 3, 3, 3);
        System.out.println(mn.majorityNumber(new ArrayList<Integer>(nums)));
    }

    public int majorityNumber(List<Integer> nums) {
        Integer temp = null;
        int count = 0;
        for (int num : nums) {
            if (count == 0) temp = num;
            if (temp == num) count++;
            else count--;
        }
        return temp;
    }
}
